package demo3;


public class TestDemo {

   /**
   * 给定3个参数，N，M，K怪兽有N滴血，等着英雄来砍自己,英雄每一次打击，
   * 都会让怪兽流失[0~M]的血量,到底流失多少？每一次在[0~M]上等概率的获得一个值,
   * 求K次打击之后，英雄把怪兽砍死的概率
   */
   //hp代表怪兽的血量
   //一刀可以砍0...M滴血  M代表有0...M滴血
   //times--->代表可以砍怪兽几次
   //求解英雄把怪兽砍死的概率.
    public static double ways1(int N,int M,int K){
        long total = (long)Math.pow(M+1,K);
        long kills = process(N,M,K);
        return (double)kills / (double) total;
    }
    //hp代表怪兽的血量
    //一刀可以砍0...M滴血  M代表有0...M滴血
    //times--->代表可以砍怪兽几次
    //求解英雄把怪兽砍死的概率.
    //这里的process,就是可以砍死多少次
    public static long process(int hp,int M,int times){
        if(times==0){
            return hp<=0 ? 1 : 0;
        }
        if(hp<=0){
            return (long)Math.pow(M+1,times);
        }
        long ways = 0;
        for(int i =0;i<=M;++i){
            //下一回的血量就是hp-i,可以砍的血量为0...M ,还剩下times -1次机会砍
            ways += process(hp-i,M,times-1);
        }
        return ways;
    }

    //改为动态规划
    //N ,K: 可变参数
    public static double dpWays(int N,int M,int K){
        //次数为行,血量为列
        long[][] dp = new long[K+1][N+1];
        dp[0][0] = 1;
        for(int times = 1;times<=K;++times){
            dp[times][0] = (long)Math.pow(M+1,times);
            for(int hp = 1;hp<=N;++hp){
                long ways = 0;
                for(int i =0;i<=M;++i){
                    //下一回的血量就是hp-i,可以砍的血量为0...M ,还剩下times -1次机会砍
                    if(hp-i>0) {
                        ways += dp[times - 1][hp - i];
                    }else {
                        ways += Math.pow(M+1,times-1);
                    }
                }
                dp[times][hp] = ways;
            }
        }
        return (double)dp[K][N] /(double)Math.pow(M+1,K);
    }

    public static double dpWays1(int N,int M,int K){
        //次数为行,血量为列
        long[][] dp = new long[K+1][N+1];
        dp[0][0] = 1;
        for(int times = 1;times<=K;++times){
            dp[times][0] = (long)Math.pow(M+1,times);
            for(int hp = 1;hp<=N;++hp){
                    //下一回的血量就是hp-i,可以砍的血量为0...M ,还剩下times -1次机会砍
                dp[times][hp] = dp[times][hp - 1] + dp[times - 1][hp];
                if(hp-M-1>0) {
                    dp[times][hp] -= dp[times-1][hp-M-1];
                }else {
                    dp[times][hp] -= (long)Math.pow(M+1,times-1);
                }
            }
        }
        return (double)dp[K][M] /(double)Math.pow(M+1,K);
    }


    public static void main(String[] args) {
        System.out.println(ways1(3, 3, 9));
        System.out.println(dpWays(3, 3, 9));
        System.out.println(dpWays1(3, 3, 9));

    }


}